#include <iostream>
using namespace std;

struct Matrix{
   unsigned long long a, b, c, d;
};


//Fibonacci O(N)
unsigned long long fib(int n){
   unsigned long long j = 1, fib = 1, tmp;
      
   for(int k = 3; k <= n; k++){
      tmp = fib;
      fib = j+fib;
      j = tmp;
   }
   return fib;
}


//Fibonacci O(logN)
Matrix fibonacci(int n){
   if(n == 1){
      Matrix m = {0,1,1,1};
      return m;
   } 
   
   Matrix x = fibonacci(n/2);
   Matrix r={x.a*x.a+x.b*x.c, x.a*x.b+x.b*x.d, x.a*x.c+x.d*x.c, x.b*x.c+x.d*x.d};

   if(n & 1){
      unsigned long long tmp = r.a;
      r.a = r.b;
      r.b += tmp;

      tmp = r.c;
      
      r.c = r.d;
      r.d += tmp;
   }   
   return r;   
}

int main(){

   for(int i = 0; i < 3000000; i++)
      fibonacci(87);

   for(int i = 0; i < 3000000; i++)
      fib(87);
   return 0;


}
